package sorting.algorithms;

import java.util.ArrayList;
import java.util.List;

public class MergeSort implements SortingAlgorithm{

	@Override
	public List<Comparable> sort(List<Comparable> toSort) {
		List<Comparable> result;
	    if (toSort.size() <= 1) {
	        result = toSort;
		} else {
		    List<Comparable> left = new ArrayList<Comparable>();
		    List<Comparable> right = new ArrayList<Comparable>();
		    
		    int middle = toSort.size() / 2 - 1;
		    for (int i = 0; i < toSort.size(); i++){
		    	if (i <= middle) {
		    		left.add(toSort.get(i));
		    	} else {
		    		right.add(toSort.get(i));
		    	}
		    }
		    result = merge(sort(left), sort(right));
		}
		return result;
	}
	
	private List<Comparable> merge(List<Comparable> left,List<Comparable> right){
	    List<Comparable> result = new ArrayList<Comparable>();
	    while (left.size() > 0 && right.size() > 0){
	            if (left.get(0).compareTo(right.get(0)) < 0) {
	                result.add(left.get(0));
	                left.remove(0);
	            } else {
	            	result.add(right.get(0));
	                right.remove(0);
	            }
	    }
	    result.addAll(left);
	    result.addAll(right);
	    return result;
	}


	@Override
	public String getName() {
		// TODO Auto-generated method stub
		return "MergeSort";
	}

}
